package com.roc.list.linkedlist;

import java.util.LinkedList;

/**
 * 手写linkedlist
 */
public class ExtLinkedList<E> {

    //链表实际存储元素
    private int size;

    //第一个元素（头节点，为了查询开始）
    private Node first;

    //最后一个元素（头节点，为添加开始）
    private Node last;

    public void add(E e) {
        //添加第一个元素
        //创建节点
        Node node = new Node();
        //为节点赋值
        node.object = e;
        if (null == first) {
            //给第一个元素node节点赋值
            first = node;
        } else {
            //添加第二个或以上元素
            node.prev = last;
            //将上一个元素的next赋值
            last.next = node;
        }
        last = node;
        //实际长度++
        size++;
    }

    public void add(int index, E e) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("数组越界啦");
        ExtLinkedList<E>.Node oldnode = getNode(index);
        if (null != oldnode) {
            ExtLinkedList<E>.Node oldprev = oldnode.prev;

            Node node=new Node();
            node.object=e;
            node.next=oldnode;
            if (null==oldprev){
                first=node;
            }else {
                node.prev=oldprev;
                oldprev.next=node;
            }
            oldnode.prev=node;
            size++;
        }

    }

    public Object get(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("数组越界啦");
        return getNode(index).object;
    }

    public Node getNode(int index) {
        Node node = null;
        if (null != first) {
            node = first;
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        }
        return node;
    }

    public void remove(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException("数组越界啦");
        ExtLinkedList<E>.Node node = getNode(index);
        if (null != node) {
            ExtLinkedList<E>.Node oldNextNode = node.next;
            ExtLinkedList<E>.Node oldPrevNode = node.prev;

            if (null == oldPrevNode) {
                first = oldNextNode;
            } else {
                oldPrevNode.next = oldNextNode;
            }
            if (null == oldNextNode) {
                last = oldPrevNode;
            } else {
                oldNextNode.prev = oldPrevNode;
            }
            size--;
        }
    }

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    class Node {
        //存放元素的值
        Object object;
        //存放第一个节点
        Node prev;
        //存放最后一个节点
        Node next;
    }

    public static void main(String[] args) {
        ExtLinkedList linkedList = new ExtLinkedList();
        linkedList.add("A");
        linkedList.add("B");
        linkedList.add("C");
        System.out.println(linkedList.get(0));
        linkedList.remove(0);
        linkedList.add(0,"A");
        System.out.println(linkedList.get(0));
    }
}
